package com.cheung.leetcode.str;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.str
 * @Author :  cheungming
 * @CreateTime : 2024-05-08 08:48:39
 * @Description : KMP算法学习
 * @Version : 1.0
 */
public class Code28Test {

    public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) {
            return 0;
        }
        // 本题使用KMP算法解决

        int n = haystack.length();
        char[] haystackCharArray = haystack.toCharArray();
        char[] needleCharArray = needle.toCharArray();
        int m = needle.length();
        // 获取前缀数组
        int[] next = prefixArray(needle);

        // 匹配计算
        int i = 0, j = 0;
        while (i < n) {
            if (haystackCharArray[i] == needleCharArray[j]) {
                i++;
                j++;
            } else {
                if (j == 0) {
                    i++;
                } else {
                    j = next[j - 1];
                }
            }

            if (j == m) {
                return i - j;
            }
        }

        return -1;
    }


    // 计算一个字符串的前缀数组
    public int[] prefixArray(String str) {
        char[] chars = str.toCharArray();
        // str = aabaaab
        int[] arr = new int[str.length()];
        int i = 1, j = 0;
        while (i < str.length()) {
            if (chars[i] == chars[j]) {
                arr[i] = j + 1;
                j++;
                i++;
            } else {
                if (j >= 1) {
                    j = arr[j - 1];
                } else {
                    arr[i] = 0;
                    i++;
                }
            }
        }

        return arr;
    }

    @Test
    public void test1() {
        String haystack = "sadbutsad", needle = "sad";
        assert 0 == strStr(haystack, needle);
    }

    @Test
    public void test2() {
        String haystack = "leetcode", needle = "leeto";
        assert -1 == strStr(haystack, needle);
    }

    @Test
    public void test3() {
        String haystack = "adcadcaddcadde";
        String needle = "adcadde";
        assert -1 == strStr(haystack, needle);
    }


    @Test
    public void test() {
        System.out.println(Arrays.toString(prefixArray("aabaaab")));
        System.out.println(Arrays.toString(prefixArray("adcadde")));
    }

}
